//
// Created by fh on 2021/6/30.
//

#include "Graph.h"

/* ******************************************* 邻接矩阵图 *********************************************** */

/* 邻接矩阵图创建初始化 */
AdjacencyMatrixGraph *AdjacencyMatrixGraphCreatAndInit(int count) {
    AdjacencyMatrixGraph *p = (AdjacencyMatrixGraph *) malloc(sizeof(AdjacencyMatrixGraph));
//    p->v_count = count;

    int t[][8] = {{0,1,0,1,0,0,0,0},
                  {1,0,1,0,1,0,0,0},
                  {0,1,0,0,0,1,0,0},
                  {1,0,0,0,1,0,0,0},
                  {0,1,0,1,0,1,1,0},
                  {0,0,1,0,1,0,0,1},
                  {0,0,0,0,1,0,0,1},
                  {0,0,0,0,0,1,1,0}};
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            (p->a)[i][j] = t[i][j];
        }
    }

    /*
    p->v = (int(*)[N]) malloc(sizeof(int) * count * count);
    for (int i = 0; i < count * count; ++i) {
        **(p->v) = -1;
        printf("%d ",**(p->v));
        (**(p->v))++;
    }
    //*/

    /*
    int b[3][3] = {{1,2,3},
                   {4,5,6},
                   {7,8,9}};
    int (*q)[3] = &b;
    for (int i = 0; i < 9; ++i) {
        printf("%d ",**q);
        (**q)++; // 1 2 3
    }
    for (int i = 0; i < 3; ++i) {
        printf("%d ",**q);
        q++; // 1 4 7
//        (**q)++; // 1 2 3
    }
    //*/

    return p;
}

/* 邻接矩阵图广度优先遍历 */
void AdjacencyMatrixGraphBFSDisplay(AdjacencyMatrixGraph *graph,int s) {

    LinkQueue *queue = LinkQueueCreateAndInit();
    int visited[N];
    for (int i = 0; i < N; ++i) {
        visited[i] = -1;
    }

    int outValue;
    LinkQueueEnQueue(queue,s);
    visited[s] = 1;

    while (queue->rear != queue->front) {
        LinkQueueDeQueue(queue,&outValue);
        printf("%d --> ",outValue);
        for (int i = 0; i < N; ++i) {
            if ((graph->a)[outValue][i] == 1 && visited[i] != 1) {
                LinkQueueEnQueue(queue,i);
                visited[i] = 1; // 入队就要标记为已经访问了,如果是在出队打印的时候才标记就有可能队伍里存在一样的结点
            }
        }
    }
    printf("结束\n");

    free(queue);
    queue = NULL;
}

/* 邻接矩阵图广度优先搜索路径 */
void AdjacencyMatrixGraphBFSSearch(AdjacencyMatrixGraph *graph,int s,int t) {
    LinkQueue *queue = LinkQueueCreateAndInit();
    int visited[N];
    for (int i = 0; i < N; ++i) {
        visited[i] = -1;
    }
    /* prev 用来记录搜索路径。当我们从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存
     * 储的就是搜索的路径。不过，这个路径是反向存储的。prev[w]存储的是，顶点 w 是从哪个前驱
     * 顶点遍历过来的。比如，我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3]就等于 2。为了
     * 正向打印出路径，我们需要递归地来打印，你可以看下 print() 函数的实现方式。
     * */
    int prev[N];
    for (int i = 0; i < N; ++i) {
        prev[i] = -1;
    }

    int outValue;
    LinkQueueEnQueue(queue,s);
    visited[s] = 1;
//    prev[s] = outValue;

    while (queue->rear != queue->front) {
        LinkQueueDeQueue(queue,&outValue);
        for (int i = 0; i < N; ++i) {
            if ((graph->a)[outValue][i] == 1 && visited[i] != 1) {
                LinkQueueEnQueue(queue,i);
                visited[i] = 1; // 入队就要标记为已经访问了,如果是在出队打印的时候才标记就有可能队伍里存在一样的结点
                prev[i] = outValue;
            }
        }
    }
    //
    for (int i = 0; i < N; ++i) {
        printf("%d ",prev[i]);
    }
    printf("\n");

    // 用栈倒着打印
    LinkStack *stack = LinkStackCreateAndInit();
    LinkStackPush(stack,t);
    int i = t;
    while (prev[i] != -1 && prev[i] != i) {
        LinkStackPush(stack,prev[i]);
        i = prev[i];
    }
    printf("最短路径: ");
    while (stack->count > 0) {
        int e;
        LinkStackPop(stack,&e);
        printf("%d --> ", e);
    }
    printf("结束\n");

    free(queue);
    queue = NULL;
}

/* 邻接矩阵图深度优先遍历 */
void AdjacencyMatrixGraphDFSDisplay(AdjacencyMatrixGraph *graph,int s,int visited[N]) {
    for (int i = 0; i < N; ++i) {
        if ((graph->a)[s][i] == 1 && visited[i] != 1) {
            printf("[%d][%d]\n",s,i);
            printf("%d ",i);
            visited[s] = 1;
            AdjacencyMatrixGraphDFSDisplay(graph,i,visited);
        }
    }
}

/* 邻接矩阵图深度优先搜索 */
void AdjacencyMatrixGraphDFSSearch(AdjacencyMatrixGraph *graph,int s,int t,int visited[N],int pre[N]) {
    visited[s] = 1;
    for (int i = 0; i < N; ++i) {
        if ((graph->a)[s][i] == 1 && visited[i] != 1) {
            printf("%d ",s);
            pre[i] = s;
            AdjacencyMatrixGraphDFSSearch(graph,i,t,visited,pre);
        }
    }

}

/* 打印邻接矩阵:数组 */
void AdjacencyMatrixGraphDisplay(AdjacencyMatrixGraph *graph) {
    printf("图: ");
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            printf("%d ",(graph->a)[i][j]);
        }
    }
    printf("\n");
}

/* 邻接矩阵图广度优先搜索demo */
void AdjacencyMatrixGraphDemo() {
    AdjacencyMatrixGraph *graph = AdjacencyMatrixGraphCreatAndInit(8);
    {
        AdjacencyMatrixGraphDisplay(graph);
    }

    {
        AdjacencyMatrixGraphBFSDisplay(graph,0);
        AdjacencyMatrixGraphBFSSearch(graph,3,7);
    }

    {
        printf("--------------------------- 邻接矩阵图的深度遍历 ------------------------\n");
        int visited[N];
        for (int i = 0; i < N; ++i) {
            visited[i] = -1;
        }
        visited[0] = 1;
        printf("%d ",0);
        AdjacencyMatrixGraphDFSDisplay(graph,0,visited);
    }

    {
        printf("\n--------------------------- 邻接矩阵图的深度搜索 ------------------------\n");
        int visited[N];
        for (int i = 0; i < N; ++i) {
            visited[i] = -1;
        }

        int pre[N];
        for (int i = 0; i < N; ++i) {
            pre[i] = -1;
        }

        int t = 4;
        AdjacencyMatrixGraphDFSSearch(graph,0,t,visited,pre);

        printf("\n");
        for (int i = 0; i < N; ++i) {
            printf("%d ",pre[i]);
        }

        // 用栈倒着打印
        LinkStack *stack = LinkStackCreateAndInit();
        LinkStackPush(stack,t);
        int i = t;
        while (pre[i] != -1 && pre[i] != i) {
            LinkStackPush(stack,pre[i]);
            i = pre[i];
        }
        printf("深度优先搜索路径: ");
        while (stack->count > 0) {
            int e;
            LinkStackPop(stack,&e);
            printf("%d --> ", e);
        }
        printf("结束\n");
    }

}




/* ******************************************* 邻接表图 *********************************************** */

/* 创建邻接表并初始化 */
AdjacencyListGraph *AdjacencyListGraphCreatAndInit(int count,int directional) {
    AdjacencyListGraph *graph = (AdjacencyListGraph *) malloc(sizeof(AdjacencyListGraph));
    graph->count = count;
    graph->directional = directional;
    for (int i = 0; i < count; ++i) {
        AdjacencyList *list = (AdjacencyList *) malloc(sizeof(AdjacencyList));
        Node *head = (Node *) malloc(sizeof(Node));
        list->head = head;
        list->head->data = -1;
        list->head->next = NULL;
        graph->array[i] = list;
    }
    return graph;
}

/* 在顶点insertIndex插入值insertValue */
Status AdjacencyListGraphInsert(AdjacencyListGraph *graph,int insertIndex,int insertValue) {
    if (insertIndex > M - 1 || insertIndex < 0 || graph == NULL || insertValue > M - 1 || insertValue < 0) {
        return ERROR;
    }
    AdjacencyList *list = graph->array[insertIndex];
    Node *p = list->head;
    // 需要判重，不需要插入相同的顶点了
    int shouldInsert = 1;
    // 在尾部插入
    while (p->next != NULL) {
        p = p->next;
        if (p->data == insertValue) {
            shouldInsert = 0;
            break;
        }
    }
    // 需要判重，不需要插入相同的顶点了
    if (shouldInsert != 0) {
        Node *createNode = (Node *) malloc(sizeof(Node));
        createNode->next = NULL;
        createNode->data = insertValue;
        p->next = createNode;
    }

    // 如果是无向图还需要双向插入
    if (graph->directional != 1) {
        Node *q = graph->array[insertValue]->head;
        int innerShouldInsert = 1;
        while (q->next != NULL) {
            q = q->next;
            if (q->data == insertIndex) {
                innerShouldInsert = 0;
                break;
            }
        }
        if (innerShouldInsert != 0) {
            Node *createNode = (Node *) malloc(sizeof(Node));
            createNode->next = NULL;
            createNode->data = insertIndex;
            q->next = createNode;
        }
    }
    return OK;
}

/* 清空顶点关系/图 */
Status AdjacencyListGraphClear(AdjacencyListGraph *graph) {
    if (graph == NULL) {
        return ERROR;
    }
    for (int i = 0; i < graph->count; ++i) {
        // 这里看看结点要不要释放
        Node *p = graph->array[i]->head->next;
        if (p == NULL) {
            continue;
        }
        Node *q = p->next;
        while (1) {
            free(p);
            p = NULL;
            p = q;
            if (q == NULL) {
                break;
            }
            q = q->next;
        }
        // 释放完链表最后要将头结点的next指向空
        graph->array[i]->head->next = NULL;
    }
    return OK;
}

/* 释放内存 */
Status AdjacencyListGraphDealloc(AdjacencyListGraph **graph) {
    AdjacencyListGraph *innerGraph = *graph;
    if (innerGraph == NULL) {
        printf("图已经是空的\n");
        return ERROR;
    }
    for (int i = 0; i < innerGraph->count; ++i) {
        AdjacencyList *list = innerGraph->array[i];
        if (list->head != NULL) {
            Node *p = list->head->next;
            if (p == NULL) {
                free(list->head);
                list->head = NULL;
                continue;
            }
            Node *q = p->next;
            while (1) {
                free(p);
                p = NULL;
                p = q;
                if (q == NULL) {
                    break;
                }
                q = q->next;
            }
            list->head->next = NULL;
            free(list->head);
            list->head = NULL;
        }
        free(list);
        list = NULL;
        innerGraph->array[i] = NULL;
    }
    free(*graph);
    *graph = NULL;
    return OK;
}

/* 邻接表图广度遍历 */
void AdjacencyListGraphBFSDisplay(AdjacencyListGraph *graph,int start) {
    printf("邻接表广度优先遍历: ");
    int *visited = (int *) malloc(sizeof(int) * (graph->count));
    for (int i = 0; i < graph->count; ++i) {
        visited[i] = -1;
    }
    LinkQueue *queue = LinkQueueCreateAndInit();
    LinkQueueEnQueue(queue,start);
    visited[start] = 1;

    int getValue;
    while (queue->front != queue->rear) {
        LinkQueueDeQueue(queue,&getValue);
        printf("%d -> ",getValue);
        AdjacencyList *list = graph->array[getValue];
        Node *p = list->head->next;
        while (p != NULL) {
            if (visited[p->data] != 1) {
                LinkQueueEnQueue(queue,p->data);
                visited[p->data] = 1;
            }
            p = p->next;
        }
    }
    printf("遍历结束\n");
}

void AdjacencyListGraphDisplayBFSRoute(int prev[],int start,int end) {
    if (prev[end] != -1 && end != start) {
        AdjacencyListGraphDisplayBFSRoute(prev,start,prev[end]);
    }
    printf("%d ",end);
}

/* 邻接表图广度搜索 */
void AdjacencyListGraphBFSSearch(AdjacencyListGraph *graph,int start,int end) {
    printf("邻接表广度优先搜索: ");
    int *visited = (int *) malloc(sizeof(int) * (graph->count));
    for (int i = 0; i < graph->count; ++i) {
        visited[i] = -1;
    }
    int *prev = (int *) malloc(sizeof(int) * (graph->count));
    for (int i = 0; i < graph->count; ++i) {
        prev[i] = -1;
    }

    LinkQueue *queue = LinkQueueCreateAndInit();
    LinkQueueEnQueue(queue,start);
    visited[start] = 1;

    int getValue;
    while (queue->front != queue->rear) {
        LinkQueueDeQueue(queue,&getValue);
        printf("%d -> ",getValue);
        AdjacencyList *list = graph->array[getValue];
        Node *p = list->head->next;
        while (p != NULL) {
            if (visited[p->data] != 1) {
                LinkQueueEnQueue(queue,p->data);
                visited[p->data] = 1;
                prev[p->data] = getValue;
                if (end == p->data) {
                    break;
                }
            }
            p = p->next;
        }
    }
    printf("遍历结束\n");

//    for (int i = 0; i < graph->count; ++i) {
//        printf("%d ",prev[i]);
//    }
//    printf("\n");

    /*
    int i = end;
    while (prev[i] != -1) {
        printf("%d ",prev[i]);
        i = prev[i];
    }
    //*/
    printf("搜索路径: ");
    AdjacencyListGraphDisplayBFSRoute(prev,start,end);
}

void recurDFSDisplay(AdjacencyListGraph *graph,int start,int visited[]) {
    printf("%d -> ",start);
    visited[start] = 1;
    AdjacencyList *list = graph->array[start];
    Node *p = list->head->next;
    while (p != NULL) {
        if (visited[p->data] != 1) {
            recurDFSDisplay(graph,p->data,visited);
        }
        p = p->next;
    }
}
/* 邻接表图深度遍历 */
void AdjacencyListGraphDFSDisplay(AdjacencyListGraph *graph,int start) {
    int *visited = (int *) malloc(sizeof(int) * graph->count);
    for (int i = 0; i < graph->count; ++i) {
        visited[i] = -1;
    }
    printf("\n邻接表深度优先遍历: ");
    recurDFSDisplay(graph,start,visited);
}

void recurDFSSearch(AdjacencyListGraph *graph,int start,int end,int visited[],int prev[],int *found) {
    if (*found == 1) {
        return;
    }
    printf("%d -> ",start);
    visited[start] = 1;
    if (start == end) {
        *found = 1;
        return;
    }
    AdjacencyList *list = graph->array[start];
    Node *p = list->head->next;
    while (p != NULL) {
        if (visited[p->data] != 1 && start != end) {
            prev[p->data] = start;
            recurDFSSearch(graph,p->data,end,visited,prev,found);
        }
        p = p->next;
    }
}
/* 邻接表图深度搜索 */
void AdjacencyListGraphDFSSearch(AdjacencyListGraph *graph,int start,int end) {
    int *visited = (int *) malloc(sizeof(int) * graph->count);
    for (int i = 0; i < graph->count; ++i) {
        visited[i] = -1;
    }
    int *prev = (int *) malloc(sizeof(int) * graph->count);
    for (int i = 0; i < graph->count; ++i) {
        prev[i] = -1;
    }
    int found = 0;
    printf("\n邻接表深度优先搜索: ");
    recurDFSSearch(graph,start,end,visited,prev,&found);

    printf("\n搜索路径: ");
    AdjacencyListGraphDisplayBFSRoute(prev,start,end);
}

/* 打印邻接表 */
void AdjacencyListGraphDisplay(AdjacencyListGraph *graph) {
    printf("--------------------------- 打印邻接表 ------------------------\n");
    if (graph == NULL) {
        printf("图是空的\n");
        return;
    }
    for (int i = 0; i < graph->count; ++i) {
        printf("[%d]: ",i);
        AdjacencyList *list = graph->array[i];
        if (list == NULL) {
            printf("\n");
            continue;
        }
        Node *p = list->head;
        while (p != NULL) {
            if (p == list->head) {
                printf("head -> ");
            } else {
                printf("%d -> ",p->data);
            }
            p = p->next;
        }
        printf("NULL\n");
    }
}



/* 邻接表图demo */
void AdjacencyListGraphDemo() {

    {
        AdjacencyListGraph *graph = AdjacencyListGraphCreatAndInit(6,0);

        printf("--------------------------- 邻接表插入测试数据 ------------------------\n");
        AdjacencyListGraphInsert(graph,1,2);

        int a[3] = {3,5,4};
        for (int i = 0; i < (sizeof(a)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,2,a[i]);
        }

        int b[2] = {1,2};
        for (int i = 0; i < (sizeof(b)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,4,b[i]);
        }

        int c[2] = {4,3};
        for (int i = 0; i < (sizeof(c)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,5,c[i]);
        }

        AdjacencyListGraphDisplay(graph);
        Status result = AdjacencyListGraphDealloc(&graph);
        AdjacencyListGraphDisplay(graph);
    }

    {
        printf("---------------------------------------------- 邻接表广度优先遍历 ------------------------------------------\n");
        AdjacencyListGraph *graph = AdjacencyListGraphCreatAndInit(8,0);
        AdjacencyListGraphDisplay(graph);

        int a[2] = {1,3};
        for (int i = 0; i < (sizeof(a)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,0,a[i]);
        }

        int b[3] = {0,2,4};
        for (int i = 0; i < (sizeof(b)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,1,b[i]);
        }

        int c[2] = {1,5};
        for (int i = 0; i < (sizeof(c)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,2,c[i]);
        }

        int d[2] = {0,4};
        for (int i = 0; i < (sizeof(d)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,3,d[i]);
        }

        int e[2] = {1,3,5,6};
        for (int i = 0; i < (sizeof(e)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,4,e[i]);
        }

        int f[2] = {2,4,7};
        for (int i = 0; i < (sizeof(f)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,5,f[i]);
        }

        int g[2] = {4,7};
        for (int i = 0; i < (sizeof(g)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,6,g[i]);
        }

        int h[2] = {5,6};
        for (int i = 0; i < (sizeof(h)/sizeof(int)); ++i) {
            AdjacencyListGraphInsert(graph,7,h[i]);
        }

        AdjacencyListGraphDisplay(graph);
        AdjacencyListGraphBFSDisplay(graph,0);
        AdjacencyListGraphBFSSearch(graph,0,6);
        AdjacencyListGraphDFSDisplay(graph,0);
        AdjacencyListGraphDFSSearch(graph,0,6);

    }


}


